UVa/610 - Street directions/610.cpp

   1 /*
   2   Problem: 610 - Street directions (UVa online judge)
   3
   4   Author: Andrés Mejía-Posada (http://github.com/andmej/acm)
   5   Algorithm: Depth-first search
   6  */
   7 #include <iostream>
   8
   9 using namespace std;
  10
  11 const int MAXN = 1000;
  12
  13 bool g[MAXN][MAXN], visited[MAXN];
  14 int n, p[MAXN]; //p[i] = nodo predecesor que me llevó al nodo i.
  15
  16 void dfs(int u){
  17   visited[u] = true;
  18   for (int v=0; v<n; ++v){
  19     if (g[u][v]){ //hay arista
  20       if (visited[v] && v != p[u]){ //encontre un ciclo
  21         g[v][u] = false;
  22         int previous = u;
  23         while(previous != v){ //Volver de una sola vía todas las aristas del ciclo
  24           g[previous][p[previous]] = false;
  25           previous = p[previous];
  26         }
  27       }else if (!visited[v]){
  28         p[v] = u;
  29         dfs(v);
  30       }
  31     }
  32   }
  33 }
  34
  35 int main(){
  36   int m, C=1;
  37   while (scanf("%d %d", &n, &m) == 2 && (n+m)){
  38     for (int i=0; i<n; ++i){
  39       for (int j=0; j<n; ++j){
  40         g[i][j] = false;
  41       }
  42       visited[i] = false;
  43       p[i] = -1;
  44     }
  45
  46     int u, v;
  47     while (m--){
  48       scanf("%d %d", &u, &v);
  49       --u, --v;
  50       g[u][v] = g[v][u] = true;
  51     }
  52
  53     dfs(0);
  54     printf("%d\n\n", C++);
  55     for(int i=0; i<n; ++i){
  56       for (int j=0; j<n; ++j){
  57         if (g[i][j]){
  58           printf("%d %d\n", i+1, j+1);
  59         }
  60       }
  61     }
  62     printf("#\n");
  63
  64   }
  65   return 0;
  66 }